package com.dexter.year2023.charpter2_reverselinklist.level1;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 206. 反转链表 ★
 * https://leetcode.cn/problems/reverse-linked-list/
 * <p>
 * 给你单链表的头结点 head ，请你反转链表，并返回反转后的链表。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 * <p>
 * 提示：
 * 链表中结点的数目范围是 [0, 5000]
 * -5000 <= Node.val <= 5000
 * <p>
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 *
 * @author Dexter
 */
public class ReverseList {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        Node head = initLinkedList(a);
        //测试方法
        int testMethod = 1;
        switch (testMethod) {
            case 1:
                // 法1：虚拟结点辅助反转
                head = reverseListByDummy(head);
                break;
            case 2:
                // 法2：双指针常规方法
                head = reverseListSimple(head);
                break;
            case 3:
                // 法3：法2的进阶，递归法
                head = reverseListByRe(head);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        printLinkedList(head);
    }

    /**
     * 法1：虚拟结点，cur每往队尾移动一步，“拆下来”的元素都接在dummy.next
     *
     * @param head
     * @return
     */
    public static Node reverseListByDummy(Node head) {
        Node dummy = new Node(-1);
        // cur移动，最后cur的指向反向
        Node cur = head;
        while (cur != null) {
            // 暂存cur下一结点信息
            Node next = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            // cur移动
            cur = next;
        }
        return dummy.next;
    }

    /**
     * 法2：不用虚拟结点的常规写法，cur正向移动，但是指向反向
     *
     * @param head
     * @return
     */
    public static Node reverseListSimple(Node head) {
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            // 暂存cur下一结点信息
            Node next = cur.next;
            // 改变cur的指向  ... -> 2 -> 1 -> null
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 法3：递归法，这个还需要理解一下
     *
     * @param head
     * @return
     */
    public static Node reverseListByRe(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node newHead = reverseListByRe(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
